package com.leetcode.动态规划;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 * @author LZF
 *
 */
public class L53最大子数组和 {
	public static void main(String[] args) {
		int result = maxSubArray(new int[] {-2,1,-3,4,-1,2,1,-5,4});
		System.out.println(result);
	}
	
	/**
	 * dp[i]:以i位置为结尾的连续子数组的最大和(注意：'和'可以为负数)
	 * dp[i]由两种情况而来
	 * if(dp[i - 1] < 0) 则 dp[i]最大应该是nums[i]本身
	 * else dp[i] = dp[i - 1] + nums[i]
	 * 
	 * 初始化
	 * dp[0] = nums[0]
	 * 
	 * 返回，返回dp数组中最大的（由dp的定义可以得到）
	 * @param nums
	 * @return
	 */
	public static int maxSubArray(int[] nums) {
		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		int result = dp[0];
		for(int i = 1;i < nums.length;i++) {
			if(dp[i - 1] < 0)
				dp[i] = nums[i];
			else 
				dp[i] = dp[i - 1] + nums[i];
			result = Math.max(result,dp[i]);
		}
		return result;
    }
}
